package oct2013.linkednode;

import java.util.Stack;

public class SymmetricTree {
	public boolean isSymmetric(TreeNode root) {
		if (root == null)
			return true;
		Stack<TreeNode> stack = new Stack<TreeNode>();
		stack.push(root.left);
		stack.push(root.right);
		while (!stack.isEmpty()) {
			TreeNode r = stack.pop();
			TreeNode l = stack.pop();
			if (l == null && r == null)
				continue;
			else if (l == null || r == null)
				return false;
			else if (l.val != r.val)
				return false;
			else {
				stack.push(l.left);
				stack.push(r.right);
				stack.push(l.right);
				stack.push(r.left);
			}
		}
		return true;
	}

	// Recursive version
	public boolean isSymmetricRecursive(TreeNode root) {
		if (root == null)
			return true;
		return dfs(root.left, root.right);
	}

	boolean dfs(TreeNode l, TreeNode r) {
		if (l == null && r == null)
			return true;
		if (l == null || r == null)
			return false;
		if (l.val != r.val)
			return false;
		return dfs(l.left, r.right) && dfs(l.right, r.left);
	}
}
